package mac10.models;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import mac10.bean.MasterBean;
import mac10.messages.PerceptionMessage;
import mac10.models.Point;
import mac10.roles.AbstractRole;
import mac10.util.AStarHeap;
import mac10.util.Node;

import de.dailab.jiactng.agentcore.knowledge.IFact;
import de.dailab.jiactng.agentcore.ontology.IAgentDescription;

public class WorldModel implements IFact {

	private static final long serialVersionUID = 65656897388859924L;
	
	public static WorldModel staticWorldModel;
	
	private Cell[][] worldGrid;
	private int[][] cowWeights;
	
	public HashMap<String, Agent> agents = new HashMap<String, Agent>();
		
	private ArrayList<Cell> switches = new ArrayList<Cell>();
	private HashMap<Integer, Cell> cows = new HashMap<Integer, Cell>();
	public HashMap<IAgentDescription, Point> agentTargets = new HashMap<IAgentDescription, Point>();
	public HashMap<Integer, Cell> getCows ()
    {
        return cows;
    }

    private int sizex;
	private int sizey;
	private int totalSteps;
	private int currStep;
	private double score;
	private int cowsInCorral;
	private int lineOfSight;
	private int perceptionsReceivedInStep;
	private long shortestDeadline;
	private Point corralCenter;
	private  int corralx0, corraly0,  corralx1, corraly1;
	private String teamName_belongsTo;

	private ArrayList<Cell> herds = new ArrayList<Cell>();
	
    public WorldModel(int sizex, int sizey, int totalSteps, int lineOfSight, 
            int corralx0, int corraly0, int corralx1, int corraly1) {
		this.sizex = sizex;
		this.sizey = sizey;
		this.totalSteps = totalSteps;
		this.lineOfSight = lineOfSight;
        this.corralCenter = new Point((corralx0+corralx1)/2, (corraly0+corraly1)/2);
        
		int minx = Math.min(corralx0, corralx1);
		int maxx = Math.max(corralx0, corralx1);
		int miny = Math.min(corraly0, corraly1);
		int maxy = Math.max(corraly0, corraly1);
		
		this.corralx0 = minx;
		this.corralx1 = maxx;
		this.corraly0 = miny;
		this.corraly1 = maxy;
		
		this.teamName_belongsTo = "";

		worldGrid = new Cell[sizex][sizey];
		cowWeights = new int[sizex][sizey];
		for (int x = 0; x < sizex; x++) {
			for (int y = 0; y < sizey; y++) {
			    cowWeights[x][y] = 1;
				if (minx <= x && x <= maxx && miny <= y && y <= maxy) {
					worldGrid[x][y] = new Cell(x, y, 0);
					worldGrid[x][y].setAllyCorral(true);
				} else
					worldGrid[x][y] = new Cell(x, y, -1);
			}
		}
		switches = new ArrayList<Cell>();
	}
	
	public WorldModel(Cell[][] worldGrid, ArrayList<Cell> switches, 
	        int totalSteps, int currStep, int lineOfSight, double score, int cowsInCorral) {
		this.worldGrid = worldGrid;
		this.sizex = this.worldGrid.length;
		this.sizey = this.worldGrid[0].length;
		this.totalSteps = totalSteps;
		this.lineOfSight = lineOfSight;
		this.currStep = currStep;
		this.score = score;
		this.cowsInCorral = cowsInCorral;
		for(int i = 0; i < switches.size(); i++) {
			this.switches.add(this.getCell(switches.get(i).getX(), switches.get(i).getY()));
		}
	}

	public synchronized void updateModel(Cell cell) 
	{
	    final int r = 5;
        int x = cell.getX();
        int y = cell.getY();
		if (cell == null
				|| worldGrid[x][y].getTimestamp() >= cell.getTimestamp())
			return;
		if (worldGrid[x][y].isUnknown())
        {
		    if(cell.isFence())
		    {
		        cowWeights[x][y] ++;
		    }
		    else if (cell.isObstacle() || cell.isSwitch())
            {
                for (int i = -r; i <= r && x+i >= 0 && x+i < sizex; i++)
                {
                    for (int j = -r; j <= r && y+j >= 0 && y+j < sizey; j++)
                    {
                        int distance = Math.max(Math.abs(i), Math.abs(j));
                        cowWeights[x+i][y+j] += r - distance;
                    }
                }
            }
        }
        
		worldGrid[x][y] = cell;
		if (cell.isSwitch()) {
			if (!switches.contains(cell))
				switches.add(cell);
		}
		if (cell.isCow()) {
			this.cows.put(cell.getCowId(), cell);
		}
	}
	
	public synchronized void updateAgents(Agent agent) {
		agents.put(agent.name, agent);
	}

	/**
	 * überschreibt die Cell unabhaengig vom timestamp nur für Testzwecke
	 * 
	 * @param cell
	 */
	public void forceUpdateModel(Cell cell) {
		worldGrid[cell.getX()][cell.getY()] = cell;
		if (cell.isSwitch()) {
			if (!switches.contains(cell))
				switches.add(cell);
		}
	}

	public Cell getCell(Point p) {
        return worldGrid[p.x][p.y];
    }
	
	public Cell getCell(int x, int y) {
		return worldGrid[x][y];
	}

	public int getHeight() {
		return sizey;
	}

	public int getWidth() {
		return sizex;
	}

	/**
     * @return the totalSteps
     */
    public int getTotalSteps ()
    {
        return totalSteps;
    }

    /**
     * @return the currStep
     */
    public int getCurrStep ()
    {
        return currStep;
    }

    /**
     * @return the score
     */
    public double getScore ()
    {
        return score;
    }

    /**
     * @return the cowsInCorral
     */
    public int getCowsInCorral ()
    {
        return cowsInCorral;
    }
    

    /**
     * @return the lineOfSight
     */
    public int getLineOfSight ()
    {
        return lineOfSight;
    }
    
    
    /**
     * @param new sting team name
     */
    public void setTeamName(String newName){
    	teamName_belongsTo = newName;
    }
    
    
    /**
     * @return the teamName_belongsTo
     */
    public String getTeamName()
    {
        return teamName_belongsTo;
    }
    
    
    public ArrayList<Cell> getNeighbours(Point p) 
    {
        return getNeighbours(p.getX(), p.getY());
    }

    public ArrayList<Cell> getNeighbours(int x, int y) 
    {
        ArrayList<Cell> neighbours = new ArrayList<Cell>();
//        for (int i = x - 1; i <= x + 1; i++)
//        {
//            for (int j = y - 1; j <= y + 1; j++)
//            {
//                if (i >= 0 && i < sizex && j >= 0 && j < sizey
//                        && (i != x || j != y))
//                    neighbours.add(worldGrid[i][j]);
//            }
//        }
        //Sortiert damit nicht Diagonalen eventuell bevorzugt werden.
        if (isInGrid(x+1, y)) neighbours.add(worldGrid[x+1][y]);
        if (isInGrid(x-1, y)) neighbours.add(worldGrid[x-1][y]);
        if (isInGrid(x, y+1)) neighbours.add(worldGrid[x][y+1]);
        if (isInGrid(x, y-1)) neighbours.add(worldGrid[x][y-1]);
        if (isInGrid(x+1, y-1)) neighbours.add(worldGrid[x+1][y-1]);
        if (isInGrid(x-1, y+1)) neighbours.add(worldGrid[x-1][y+1]);
        if (isInGrid(x+1, y+1)) neighbours.add(worldGrid[x+1][y+1]);
        if (isInGrid(x-1, y-1)) neighbours.add(worldGrid[x-1][y-1]);
        
		return neighbours;
	}

	public ArrayList<Cell> getNeighbours4(int x, int y) {
		ArrayList<Cell> neighbours = new ArrayList<Cell>();
		for (int i = x - 1; i <= x + 1; i++) {
			for (int j = y - 1; j <= y + 1; j++) {
				if ((i == x - 1 && j == y - 1) || (i == x + 1 && j == y - 1)
						|| (i == x - 1 && j == y + 1)
						|| (i == x + 1 && j == y + 1))
					continue;
				if (i >= 0 && i < sizex && j >= 0 && j < sizey
						&& (i != x || j != y))
					neighbours.add(worldGrid[i][j]);
			}
		}
		return neighbours;
	}
	
	public Cell getNearstCellInGrid(Point p)
	{
		return getNearstCellInGrid(p.x, p.y);
	}
	
	
	public Cell getNearstCellInGrid (int x, int y)
	{
		if(x < 0)
			x = 0;
		if(x >= sizex)
			x = sizex-1;
		if(y < 0)
			y = 0;
		if(y >= sizey)
			y = sizey-1;
		
		return worldGrid[x][y];
	}

	/**
	 * @param a
	 * @param b
	 * @return the distance as max-norm
	 */
	public static int getDistance(Point a, Point b) {
		return a.maxNorm(b);
	}

	/**
	 * @param a
	 * @param b
	 * @return the distance as euclidean norm
	 */
	public static double getDistanceDouble(Cell a, Cell b) {
		return a.euklNorm(b);
	}

	/**
	 * @param start
	 * @param goal
	 * @param deadline
	 * @return the distance in cells
	 */
    public int getDistanceCells (Cell start, Cell goal, long deadline,
            boolean avoidAgents, boolean avoidCows, boolean avoidOpenFences,
            boolean avoidClosedFences)
    {
        AStarHeap astar = new AStarHeap(this, start, goal);
        astar.setAvoidAgents(avoidAgents);
        astar.setAvoidCows(avoidCows);
        astar.setAvoidOpenFences(avoidOpenFences);
        astar.setAvoidClosedFences(avoidClosedFences);
        Node to = astar.AStar(deadline);
        if (to == null)
            return -1;
        else
            try
            {
                return AbstractRole.nodeToActionStrings(to).size();
            }
            catch (Exception e)
            {
                return -1;
            }
    }

	public ArrayList<Cell> findUnattendedSwitches() {
		ArrayList<Cell> unattendedSwitches = new ArrayList<Cell>();
		for (Cell cell : switches) {
			ArrayList<Cell> tmp = getSwitchOpeningCells(cell.getX(), cell
					.getY());
			boolean unattended = true;
			for (Cell neighbour : tmp) {
				if (neighbour.isAllyAgent()) {
					unattended = false;
					break;
				}
			}
			if (unattended)
				unattendedSwitches.add(cell);
		}
		return unattendedSwitches;
	}

	public ArrayList<Cell> getSwitches() {
		return this.switches;
	}

	public Cell findCellToOpenFence(Cell currentPos, Cell fence) {
		Cell switchPos = getFenceSwitch(fence);
		if (switchPos == null)
			return null;
		double distance = Double.MAX_VALUE;
		Cell nearestCell = null;
		Cell cell = null;
		if (switchPos.getX() + 1 < getWidth()) {
			cell = getCell(switchPos.getX() + 1, switchPos.getY());
			if (cell.equals(currentPos))
				return currentPos;
			if (cell.isAccessible() && !cell.isFence()
					&& WorldModel.getDistanceDouble(currentPos, cell) < distance) {
				nearestCell = cell;
				distance = WorldModel.getDistanceDouble(currentPos, cell);
			}
		}
		if (switchPos.getX() - 1 > 0) {
			cell = getCell(switchPos.getX() - 1, switchPos.getY());
			if (cell.equals(currentPos))
				return currentPos;
			if (cell.isAccessible() && !cell.isFence()
					&& WorldModel.getDistanceDouble(currentPos, cell) < distance) {
				nearestCell = cell;
				distance = WorldModel.getDistanceDouble(currentPos, cell);
			}
		}
		if (switchPos.getY() + 1 < getHeight()) {
			cell = getCell(switchPos.getX(), switchPos.getY() + 1);
			if (cell.equals(currentPos))
				return currentPos;
			if (cell.isAccessible() && !cell.isFence()
					&& WorldModel.getDistanceDouble(currentPos, cell) < distance) {
				nearestCell = cell;
				distance = WorldModel.getDistanceDouble(currentPos, cell);
			}
		}
		if (switchPos.getY() - 1 > 0) {
			cell = getCell(switchPos.getX(), switchPos.getY() - 1);
			if (cell.equals(currentPos))
				return currentPos;
			if (cell.isAccessible() && !cell.isFence()
					&& WorldModel.getDistanceDouble(currentPos, cell) < distance) {
				nearestCell = cell;
				distance = WorldModel.getDistanceDouble(currentPos, cell);
			}
		}
		return nearestCell;
	}

    public Cell getFenceSwitch (Cell fencePos)
    {
        if (fencePos.isSwitch())
            return fencePos;

        if (!worldGrid[fencePos.getX()][fencePos.getY()].isFence())
            System.err.println("Tried to find switch of no fence "
                    + fencePos.toStringShort());

        int x = fencePos.getX();
        int y = fencePos.getY();
        Cell cell = new Cell(fencePos.getX(), fencePos.getY(), -1);
        cell.setFence(true);
        
        boolean fenceLeft = false;
        boolean fenceRight = false;
        if (x - 1 > 0)
            fenceLeft = getCell(x - 1, y).isFence();
        
        if (x + 1 < getWidth())
            fenceRight = getCell(x + 1, y).isFence();
        
        if (fenceLeft || fenceRight)
        {
            while (cell.isFence() && x > 0)
            {
                cell = getCell(--x, y);
                if (cell.isSwitch())
                    return cell;
            }
            cell = new Cell(fencePos.getX(), fencePos.getY(), -1);
            cell.setFence(true);
            x = fencePos.getX();
            while (cell.isFence() && x < getWidth()-1)
            {
                cell = getCell(++x, y);
                if (cell.isSwitch())
                    return cell;
            }
        }
        else
        {
            while (cell.isFence() && y > 0)
            {
                cell = getCell(x, --y);
                if (cell.isSwitch())
                    return cell;
            }
            cell = new Cell(fencePos.getX(), fencePos.getY(), -1);
            cell.setFence(true);
            y = fencePos.getY();
            while (cell.isFence() && y < getHeight()-1)
            {
                cell = getCell(x, ++y);
                if (cell.isSwitch())
                    return cell;
            }
        }
        return null;
    }

	public ArrayList<Cell> getSwitchOpeningCells(int x, int y) {
		ArrayList<Cell> cells = new ArrayList<Cell>();
		if (x >= 0 && x < sizex && y >= 0 && y < sizey) {
			if (x > 0 && !worldGrid[x - 1][y].isFence() && !worldGrid[x - 1][y].isObstacle())
				cells.add(worldGrid[x - 1][y]);
			
			if (x + 1 < sizex && !worldGrid[x + 1][y].isFence() && !worldGrid[x + 1][y].isObstacle())
				cells.add(worldGrid[x + 1][y]);
			
			if (y > 0 && !worldGrid[x][y - 1].isFence() && !worldGrid[x][y - 1].isObstacle())
				cells.add(worldGrid[x][y - 1]);
			
			if (y + 1 < sizey && !worldGrid[x][y + 1].isFence() && !worldGrid[x][y + 1].isObstacle())
				cells.add(worldGrid[x][y + 1]);
		}
		return cells;
	}

	public Node existsPath(Cell start, Cell goal, long deadline,
            boolean avoidAgents, boolean avoidCows, boolean avoidOpenFences,
            boolean avoidClosedFences)
    {
        AStarHeap astar = new AStarHeap(this, start, goal);
        astar.setAvoidAgents(avoidAgents);
        astar.setAvoidCows(avoidCows);
        astar.setAvoidOpenFences(avoidOpenFences);
        astar.setAvoidClosedFences(avoidClosedFences);
		Node to = astar.AStar(deadline);
		return to;
	}
	
	public synchronized long processPerception(PerceptionMessage message) {
		int step = message.getStep();
		if (step < currStep)
		{
			System.err.println("processing old perception currStep: "+currStep+" perception step: "+step);
			return -1;
		}
		if (step > currStep) {
			perceptionsReceivedInStep = 0;
			currStep = step;
			cowsInCorral = message.getCowsInCorral();
			score += cowsInCorral/((double)totalSteps);
			shortestDeadline = Long.MAX_VALUE;
		}
		perceptionsReceivedInStep++;
		if (message.getDeadline() < shortestDeadline)
			shortestDeadline = message.getDeadline();

		ArrayList<Cell> cells = message.getCells();
		// log.info("perceptions received in step "+this.simulationStep+": "+this.perceptionsReceivedInStep);
		for (Cell cell : cells) {
			updateModel(cell);
		}
		if (perceptionsReceivedInStep == MasterBean.agents.size())
			return shortestDeadline;
		else
			return -1;
	}

    public ArrayList<Point> getFencesForSwitch (Point button)
    {
        int x = button.getX();
        int y = button.getY();
        if(!worldGrid[x][y].isSwitch())
        {
            System.out.println("kein switch in getFence "+worldGrid[x][y]);
            return null;
        }
        ArrayList<Point> fence = new ArrayList<Point>();
        if (x-1 > 0 && worldGrid[x-1][y].isFence())
        {
            x--;
            fence.add(worldGrid[x][y]);
            x--;
            while (x >= 0 && worldGrid[x][y].isFence())
            {
                fence.add(worldGrid[x][y]);
                x--;
            }
            return fence;
        }
        else if (x+1 < sizex && worldGrid[x+1][y].isFence())
        {
            x++;
            fence.add(worldGrid[x][y]);
            x++;
            while (x < sizex && worldGrid[x][y].isFence())
            {
                fence.add(worldGrid[x][y]);
                x++;
            }
            return fence;
        }
        else if (y-1 > 0 && worldGrid[x][y-1].isFence())
        {
            y--;
            fence.add(worldGrid[x][y]);
            y--;
            while (y >= 0 && worldGrid[x][y].isFence())
            {
                fence.add(worldGrid[x][y]);
                y--;
            }
            return fence;
        }
        else if (y+1 < sizey && worldGrid[x][y+1].isFence())
        {
            y++;
            fence.add(worldGrid[x][y]);
            y++;
            while (y < sizey && worldGrid[x][y].isFence())
            {
                fence.add(worldGrid[x][y]);
                y++;
            }
            return fence;
        }
        else
        {
            return fence;
        }
    }
    
    /**
	 * saves the worldmodel to hard disk
	 * 
	 * previously it saves it as a temporary file and after a successful write operation
	 * it renames the file and removes the oldest file
	 * 
	 * only 3 worldmodel files are stored at the time
	 * 
	 * Template: "worldmodels/WorldModel_+wm.getTeamName()+"_""+simulationID+"_"+simulationStep+".wmodel"
	 * 
	 * @param WorldModel
	 * @return boolean
	 */
	public static boolean saveWorldModelToFile(WorldModel wm, int simulationID, int simulationStep){
		//System.out.println("start_save: "+System.currentTimeMillis());
		//long test_start = System.currentTimeMillis();
		OutputStream stream = null;
		
		File checkFile = new File("worldmodels/");
		if(!checkFile.exists()){
			checkFile.mkdir();
		}
		
		//save as temporary file
		try {
		  	stream = new FileOutputStream( "worldmodels/tmp_WorldModel_"+wm.getTeamName()+"_"+simulationID+"_"+simulationStep+".wmodel" ); 
		  	ObjectOutputStream oos = new ObjectOutputStream( stream ); 
		  	//System.out.println("WM_save_currentStep: "+ wm.getCurrStep());
		  	oos.writeObject( wm );
			oos.close();
			stream.close();
		} catch ( IOException e ) {
			//error handling?
			System.err.println( e );
			//System.out.println("1.false: "+System.currentTimeMillis());
			return false;
		}
		
		
		//rename temporary file
		File oldFile = new File("worldmodels/tmp_WorldModel_"+wm.getTeamName()+"_"+simulationID+"_"+simulationStep+".wmodel");
		File newFile = new File("worldmodels/WorldModel_"+wm.getTeamName()+"_"+simulationID+"_"+simulationStep+".wmodel");
		boolean success = oldFile.renameTo(newFile);
		oldFile.delete();

		//delete oldest file
		if(success){
			File[] files = (new File("worldmodels/")).listFiles();
			String fileName = "";
			int lowestVersionNumber = Integer.MAX_VALUE;
			int counter = 0;
			
			if (files != null && files.length > 3) { 
				for (int i = 0; i < files.length; i++) {
					fileName = files[i].getName();
					String[] splitted = fileName.split("_");
					if(Integer.parseInt(splitted[2]) != simulationID) continue;
					splitted = splitted[3].split("\\.");
					int tmp = Integer.parseInt(splitted[0]);
					//System.out.println("LOWESTVERSIONNUMBER "+ lowestVersionNumber);
					if(lowestVersionNumber > tmp){
						lowestVersionNumber = tmp;
						counter = i;
					}
				}
				files[counter].delete();
			} 
			//System.out.println("end_save: "+System.currentTimeMillis());
			//System.out.println(System.currentTimeMillis()-test_start);
			return true;
		}
		//System.out.println("2.false: "+System.currentTimeMillis());
		return false;
	}

	
	/**
	 * loads the newest file on the hard disk
	 * 
	 * Template: "worldmodels/WorldModel_"+wm.getTeamName()+"_"+simulationID+"_"+simulationStep+".wmodel"
	 * 
	 * @return WorldModel
	 */
	public static WorldModel loadWorldModelFromFile(int simulationID){
		//System.out.println("start_load: "+System.currentTimeMillis());
		//long test_start = System.currentTimeMillis();
		
		WorldModel wm;
		InputStream stream = null; 
		boolean foundIt = false;
		File directory = new File("worldmodels/");
		
		File[] files = directory.listFiles();
		String fileName = "";
		int highestVersionNumber = Integer.MIN_VALUE;
		int counter = 0;
		
		if (files != null) { 
			for (int i = 0; i < files.length; i++) {
				fileName = files[i].getName();
				String[] splitted = fileName.split("_");
				if(Integer.parseInt(splitted[2]) != simulationID) continue;
				splitted = splitted[3].split("\\.");
				int tmp = Integer.parseInt(splitted[0]);
				if(highestVersionNumber < tmp){
					//System.out.println("tmp="+tmp);
					highestVersionNumber = tmp;
					counter = i;
					foundIt = true;
				}
			}
			
			if(!foundIt){
				//System.out.println("1.null: "+System.currentTimeMillis());
				return null;
			}
			
			try { 
				stream = new FileInputStream( files[counter]); 
			 	ObjectInputStream ois = new ObjectInputStream( stream ); 
			 	wm = (WorldModel) ois.readObject(); 
			 
			 	ois.close();
				stream.close();
				//System.out.println("end_load: "+System.currentTimeMillis());
				
				//System.out.println("WM_load_currentStep: "+ wm.getCurrStep());
				//System.out.println(System.currentTimeMillis()-test_start);
				return wm;
			} 
			catch ( IOException e ) { 
				System.err.println( e ); 
				//System.out.println("2.null: "+System.currentTimeMillis());
				return null;
			} 
			catch ( ClassNotFoundException e ) {
				System.err.println( e );
				//System.out.println("3.null: "+System.currentTimeMillis());
				return null;
			} 
		}
		return null;
	}
	
	/**
	 * deletes the used save files of the world model
	 * 
	 * Template: "worldmodels/WorldModel_"+wm.getTeamName()+"_"+simulationID+"_"+simulationStep+".wmodel"
	 * 
	 * @param simulationID
	 * @return true if all files are deleted
	 */
	public static void eraseOldWorldModels(int simulationID){
			File[] files = (new File("worldmodels/")).listFiles();
			String fileName = "";
			
			if (files != null && files.length > 0) { 
				for (int i = 0; i < files.length; i++) {
					fileName = files[i].getName();
					
					String[] splitted = fileName.split("_");
					int tmp = Integer.parseInt(splitted[2]);
					
					if(simulationID == tmp){
						files[i].delete();
					}
				}
			} 
	}
	
	
	public ArrayList<Cell> getCowsAsCellList()
	{
	    ArrayList<Cell> list = new ArrayList<Cell>(cows.values());
	    
	    return list;
	}
	

    public ArrayList<Cell> getCowNeighbours(final Point p, int r)
    {
        ArrayList<Cell> cowNeighbours = new ArrayList<Cell>();
        ArrayList<Cell> open = new ArrayList<Cell>();
        ArrayList<Cell> closed = new ArrayList<Cell>();
        if(getCell(p).isCow())
        {
            cowNeighbours.add(getCell(p));
        }
        open.add(getCell(p));
        closed.add(getCell(p));
        
        while (!open.isEmpty())
        {
            Cell cell = open.remove(open.size()-1);
            ArrayList<Cell> neighbours = getNeighbours(cell);
            for (Cell n : neighbours)
            {
                if(!closed.contains(n) && herds.contains(n) && !n.isObstacle() && !n.isSwitch() && !isInSaveCorral(n))
                {
                    open.add(n);
                    if(n.isCow())
                    {
                        cowNeighbours.add(n);
                    }
                }
                closed.add(n);
            }
        }
        
        return cowNeighbours;
    }
    
    /**
     * 
     * @param point
     * @param range
     * @return
     */
    public ArrayList<Cell> getCowNeighboursForCluster(Point point, int range){
    	//begin
    	int x = point.x;
        int y = point.y;
        ArrayList<Cell> list = new ArrayList<Cell>();
        list.add(worldGrid[x][y]);
                
    	boolean[][] grid = new boolean[1 + (2 * range)][1 + (2 * range)];
    	for(int xIndex = 0; xIndex < grid.length; xIndex++){
    		for(int yIndex = 0; yIndex < grid[xIndex].length; yIndex++){
    			grid[xIndex][yIndex] = true;
    		}
    	}
        
    	//set fields to false beyond the borders
    	for (int i = x - range; i <= x + range; i++)
        {
            for (int j = y - range; j <= y + range; j++)
            {
                if (i < 0 && i >= sizex && j < 0 && j >= sizey)
                    grid[i-x+range][j-y+range] = false;
            }
        }
    	
    	//set fields hidden by obstacles to false
    	for (int i = grid.length-1; i >= 0; i--) //x
        {
            for (int j = grid[i].length-1; j >= 0; j--)//y
            {
               if(grid[i][j] == true){
            	   if((i + x - range) < 0 || (i + x - range) >= sizex || (j + y - range) < 0 || (j + y - range) >= sizey){
            		   continue;
            	   }
            	   
            	   if(worldGrid[i + x - range][j + y - range].isObstacle() && worldGrid[i + x - range][j + y - range].isFence()){
            		   grid[i][j] = false; //set field with obstacle false
            		   if(0 == i - range){
            			   //obstacle is on the same x-column as the center-cow
            			   if(0 == j - range){
                			   //obstacle is on the same y-row as the center-cow
                			   //shouldn't happen, center cow lives here
            				   System.err.println("ERROR: An obstacle or a fence is on the same point as the center cow");
                		   }else{
                			   if(0 > j - range){
                				   for(int n = j; n < grid[0].length; n++){
                					   for(int m = -(n-j); m < (n-j); m++){
                						   grid[i + m][n] = false;
                					   }
                				   }
                			   }else{
                				   for(int n = j; n >= 0; n--){
                					   for(int m = -(j-n); m < (j-n); m++){
                						   grid[i + m][n] = false;
                					   }
                				   }
                			   }
                		   }
            		   }else{
            			 //obstacle is not on the same x-column as the center-cow
            			   if(0 > i - range){
            				   if(0 == j - range){
            					   for(int n = i; n < grid.length; n++){
                					   for(int m = -(n-i); m < (n-i); m++){
                						   grid[n][j + m] = false;
                					   }
                				   }
                    		   }else{
                    			   if(0 > j - range){
                    				   for(int n = i; n < grid.length; n++){
                    					   for(int m = j; m < grid[0].length; m++){
                    						   grid[n][m] = false;
                    					   }
                    				   }
                    			   }else{//0 < j - range
                    				   for(int n = i; n < grid.length; n++){
                    					   for(int m = j; m >= 0; m--){
                    						   grid[n][m] = false;
                    					   }
                    				   }
                    			   }
                    		   }
            			   }else{ //0 < i - range
            				   if(0 == j - range){
            					   for(int n = i; n >= 0; n--){
                					   for(int m = -(i-n); m < (i-n); m++){
                						   grid[n][j + m] = false;
                					   }
                				   }
                    		   }else{
                    			   if(0 > j - range){
                    				   for(int n = i; n >= 0; n--){
                    					   for(int m = j; m < grid[0].length; m++){
                    						   grid[n][m] = false;
                    					   }
                    				   }
                    			   }else{//0 < j - range
                    				   for(int n = i; n >= 0; n--){
                    					   for(int m = j; m >= 0; m--){
                    						   grid[n][m] = false;
                    					   }
                    				   }
                    			   }
                    		   }
            			   }
            		   }
            	   }
               }
            }
        }
    	
    	//add cows to list
    	for (int i = x - range; i <= x + range; i++)
        {
            for (int j = y - range; j <= y + range; j++)
            {
                if (i >= 0 && i < sizex && j >= 0 && j < sizey
                        && (i != x || j != y) && worldGrid[i][j].isCow() && grid[i][j])
                    list.add(worldGrid[i][j]);
            }
        }
    	
    	
    	return list;
    }

    /**
     * @return the cowWeight at position (x,y)
     */
    public int getCowWeight (int x, int y)
    {
        return cowWeights[x][y];
    }

    /**
     * @return the corralCenter
     */
    public Point getCorralCenter ()
    {
        return corralCenter;
    }
    
    public boolean isInCorral (Point p)
    {              
        
        return (corralx0  <= p.x && p.x <= corralx1)
                && (corraly0  <= p.y && p.y <= corraly1);     
                
    }
    
    private ArrayList<Point> corralButNot;
    private int corralButNotStep = -1;
    //zum weiter reintreiben
    public synchronized boolean isInSaveCorral(Point p)
    {
        if(currStep != corralButNotStep)
        {
            corralButNotStep = currStep;
            corralButNot = new ArrayList<Point>();
            for (int x = corralx0 ; x <= corralx1; x++)
            {
                for (int y = corraly0; y <= corraly1; y++)
                {
                    ArrayList<Cell> neighbours = getNeighbours(x, y);
                    for (Cell cell : neighbours)
                    {
                        if(!isInCorral(cell) && cell.isAccessible() )
                        {
                            corralButNot.addAll(neighbours);
                            break;
                        }
                            
                    }
                    
                    
                }
            }        
        }
        return (!corralButNot.contains(p) && isInCorral(p));
    }

    public void removeMarkedFlags ()
    {
        for (int i = 0; i < worldGrid.length; i++)
        {
            for (int j = 0; j < worldGrid[0].length; j++)
            {
                worldGrid[i][j].setMarked(Cell.UNMARKED);
            }
        }
    }
    public boolean isInGrid(Point p)
    {
        return isInGrid(p.x, p.y);
    }
    
    public boolean isInGrid(int x, int y)
    {
        return x>=0 && x<sizex && y>=0 && y<sizey;
    }
    
    
    public synchronized void removeCowsWithUnknownLocation()
    {
        for (Iterator<Integer> iterator = cows.keySet().iterator(); iterator.hasNext();)
        {
            Integer id = (Integer) iterator.next();
            Cell cow = cows.get(id);
            if(!worldGrid[cow.x][cow.y].isCow())
            {
                iterator.remove();
            }
            
        }
    }

	public void computeEdgeDetection() {
		for (int i = 1; i < sizex - 1; i++) {
			for (int j = 1; j < sizey - 1; j++) {
				Cell cell = worldGrid[i][j];
				
				int edgeValue = 0;
				
				for (int k = -1; k < 2; k++) {
					for (int l = -1; l < 2; l++) {
						if (worldGrid[i + k][j + l].isCow()) {
							edgeValue++;
						}
					}
				}
				
				cell.edgeValue = edgeValue;
				
				if (edgeValue > 0) {
					herds.add(cell);
				}
			}
		}
		
	}
	
	public void clearHerds() {
		herds.clear();
	}

	public ArrayList<Cell> getHerds() {
		return herds;
	}
}
